package 左哥算法.ch08前缀树;

/**
 * 数组形式
 */
public class Trie {
    int pass;   //有多少个单词通过该节点
    int end;    //有多少个单词以该节点结尾
    Trie[] nexts;       //该节点通往的节点

    public Trie(int pass, int end) {
        this();
        this.pass = pass;
        this.end = end;
    }

    public Trie() {
        this.nexts = new Trie[26];
    }

    /**
     * 插入操作：
     *      依次对字符串进行遍历，每走到一个节点，对该点pass++，
     *      如果不能走通则对下一个节点进行新建，并将其放入当前节点的nexts中
     */
    public void insert(String word){
        char[] chars = word.toCharArray();
        Trie curr=this;
        for (char c : chars) {
            curr.pass++;
            Trie trieNode = curr.nexts[c-'a'];
            if (trieNode==null) {
                trieNode=new Trie();
                curr.nexts[c-'a']=trieNode;
            }
            curr=trieNode;
        }
        curr.pass++;
        curr.end++;
    }

    /**
     * 查找该单词出现的次数
     */
    public boolean search(String word){
        char[] chars = word.toCharArray();
        Trie curr=this;
        for (char c : chars) {
            curr = curr.nexts[c-'a'];
            if (curr==null){
                return false;
            }
        }
        return curr.end>0;
    }

    /**
     * 获取该前缀出现过多少次
     */
    public boolean startsWith(String prefix) {
        char[] chars = prefix.toCharArray();
        Trie curr=this;
        for (char c : chars) {
            curr = curr.nexts[c-'a'];
            if (curr==null){
                return false;
            }
        }
        return curr.pass>0;
    }
}
